package com.sam.book;

import java.util.Random;

/**
 * 布谷鸟散列 - 查找为O(1)
 * Created by samwang on 2018/1/6.
 */
public class CuckooHashTable<T> {

    /**
     * 最大装载，如果装填因子超过此限时，则执行自动表扩展
     */
    private static final double MAX_LOAD = 0.4;
    /**
     * 如果替换执行过长，指定要执行多少次再散列，理论上可以无限大，因为我们期望需要再散列的次数是一个非常小的常数
     * 实际上，这取决于如散列函数的个数、质量以及装填因子，再散列过程显著变慢，所以表扩展是值得的
     */
    private static final int ALLOWED_REHASHES = 1;
    private static final int DEFAULT_TABLE_SIZE = 101;

    private final HashFaimly<? super T> hashFunctions;
    private final int numHashFunctions;
    private T[] array;
    private int currentSize;


    public CuckooHashTable(HashFaimly<? super T> hashFunctions){
        this(hashFunctions, DEFAULT_TABLE_SIZE);
    }

    public CuckooHashTable(HashFaimly<? super T> hashFunctions, int size) {
        allocateArray(nextPrime(size));

        this.hashFunctions = hashFunctions;
        this.numHashFunctions = hashFunctions.getNumberOfFunctions();
    }

    private void allocateArray(int arraySize) {
        array = (T[]) new Object[arraySize];
    }

    private void clear() {
        currentSize = 0;
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
    }

    private int myHash(T t, int which) {
        int hashVal = hashFunctions.hash(t, which);
        hashVal %= array.length;
        if (hashVal < 0) {
            hashVal += array.length;
        }
        return hashVal;
    }

    private int findPos(T t) {
        for (int i = 0; i < numHashFunctions; i++) {
            int pos = myHash(t, i);
            if (array[pos] != null && array[pos].equals(t)) {
                return pos;
            }
        }
        return -1;
    }

    private boolean contains(T t) {
        return findPos(t) != -1;
    }

    public boolean remove(T t) {
        int pos = findPos(t);
        if (pos != -1) {
            array[pos] = null;
            currentSize--;
            return true;
        }
        return false;
    }

    public boolean insert(T t) {
        if (contains(t)) {
            return false;
        }

        if (currentSize >= array.length * MAX_LOAD) {
            expand();
        }

        return insertHelper1(t);
    }

    private void expand() {
        rehash((int) (array.length / MAX_LOAD));
    }

    private void rehash() {
        hashFunctions.generateNewFunctions();
        rehash(array.length);
    }

    private void rehash(int newLength) {
        T[] oldArray = array;
        allocateArray(nextPrime(newLength));
        currentSize = 0;
        for (T t : oldArray) {
            if (t != null) {
                insert(t);
            }
        }
    }


    private int rehashes = 0;
    private Random r = new Random();

    private boolean insertHelper1(T t) {
        final int COUNT_LIMIT = 100;
        while (true) {
            int lastPos = -1;
            int pos;

            for (int count = 0;count<COUNT_LIMIT;count++) {
                for (int i = 0; i < numHashFunctions; i++) {
                    pos = myHash(t, i);
                    if (array[pos] != null) {//如果未存在则直接插入
                        array[pos] = t;
                        currentSize++;
                        return true;

                    }
                }

                //如果已存在，则将位置替换继续循环，将替换掉的值循环插入。
                int i = 0;
                do {
                    pos = myHash(t, r.nextInt(numHashFunctions));
                } while (pos == lastPos && i++ < 5);//找出与上次不同的位置，最多5次（为了缓解笔记中的最后一个问题）

                T temp = array[lastPos = pos];
                array[pos] = t;
                t = temp;
            }

            //如果替换次数超过限制，则执行拓展或再散列
            if (++rehashes > ALLOWED_REHASHES) {//再散列次数超过限制则进行拓展
                expand();
                rehashes = 0;
            } else {//再散列
                rehash();
            }

        }


    }

    private static int nextPrime(int n) {
        while (!isPrime(n + 1)) {
            n++;
        }
        return n;

    }

    private static boolean isPrime(int n){
        for (int i = 2; i <= Math.sqrt(n); i++) {

            if (i > 2 && i%2==0){
                continue;
            }

            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }




    /**
     *
     * 将散列函数发送给布谷鸟散列的简单接口
     * @param <E>
     */
    public interface HashFaimly<E> {
        int hash(E e, int which);

        int getNumberOfFunctions();

        void generateNewFunctions();

    }

    public static class StringHashFamily implements HashFaimly<String> {

        private final int[] MULTIPLIERS;
        private final Random r = new Random();

        public StringHashFamily(int d) {
            MULTIPLIERS = new int[d];
            generateNewFunctions();
        }

        @Override
        public int hash(String s, int which) {
            final int multiplier = MULTIPLIERS[which];
            int hashVal = 0;

            for (int i = 0; i < s.length(); i++) {
                hashVal = multiplier * hashVal + s.charAt(i);
            }
            return hashVal;
        }

        @Override
        public int getNumberOfFunctions() {
            return MULTIPLIERS.length;
        }

        @Override
        public void generateNewFunctions() {
            for (int i = 0; i < MULTIPLIERS.length; i++) {
                MULTIPLIERS[i] = r.nextInt();
            }
        }
    }

}

